Requests for information from n database (typically called "database queries") generally involve a number of steps (herein called "tasks") and often the results of one or more tasks in a query (hereinafter called "job") are used in a latex task in the same job. This is called a precedence constraint because any such earlier task(s) within a job (which produce a result that is used in another task) must be completed before (i.e., must "precede") the start of execution of any such later task which uses such a result.
A parallel processing system provides a plurality of processing elements, each of which can execute a whole task of a job or a portion of such a task at the same time that the other processing elements are processing other tasks or task portions of the same or different task or job. When multiple jobs are to be scheduled for execution simultaneously on a parallel processing system, the objective typically is to create a schedule that results in completion of the last task of the total number of tasks in all of the jobs in the minimum amount of time, while respecting all of the precedence constraints among tasks of course.
For purposes of this invention, it is assumed that each processing clement in the parallel processing system (hereinafter called a "processor" rather than a processing element) will process only a single task (either alone or in combination with one or more other processors) at one time and will process it to completion (either alone or in combination with one or more other processors) before becoming available for starting another task. If a physical resource of a parallel processing system can process more than one task at the same time, it is viewed simply as more than one processor.
It is assumed also that each job has an execution time which is a nonincreasing function of the number of processors allotted to it. The execution time for a job cannot increase with an increase in the number of processors allocated to execution of the job because if the USE of an additional processor actually makes the job take longer to complete, then the best schedule would just IDLE that added processor, so that the execution time for the job at least would not increase as a consequence of adding another processor.
The problem is to find an allotment of processors (i.e., number of processors to use) for each job, and, overall, a schedule assigning the tasks of all of the jobs to the processors which respects any precedence constraints, in a manner which minimizes the completion time of the last task to finish.
Consider therefore a multiprocessor computer system consisting of P processors, and a set of N tasks which are to be scheduled on this system. The tasks may be partially ordered by a precedence relation &lt;. Assume that each task j.epsilon.{1 , . . . , N} can be allotted an arbitrary number of processors .beta..sub.j .epsilon.{1 , . . . , P}, and that its task execution time t.sub.j (.beta..sub.j)&gt;0 is a nonincreasing function of the number of allotted processors. All of the processors allotted to a task are required to execute that task in unison. That is, these .beta..sub.j processors are all required to start task j at some starting time, say .tau..sub.j. They will then complete task j at some later completion time .tau..sub.j +t.sub.j (.beta..sub.j). A schedule will consist, for each task j.epsilon.{1 , . . . , N}, of a processor allotment .beta..sub.j, and a starting time .tau..sub.j. A schedule is required to be legal in the following two senses:
For any time .tau., the number of active processors does not exceed the total number of processors. In other words, ##EQU1## If one task j.sub.1 has precedence over another task j.sub.2 then the second task cannot begin until the first task completes. In other words, if j.sub.1 &lt;j.sub.2, then .tau..sub.j1 +t.sub.j1 (.beta..sub.j1).ltoreq..tau..sub.j2.
The problem is to find an optimal schedule, one For which the overall makespan given by ##EQU2## is minimized. In other words, the goal is to minimize the latest task completion time. This will be called the malleable scheduling problem.
FIG. 1 is a block diagram illustrating the malleable scheduling problem for three jobs. The input consists of the tasks of the three jobs, represented by the nodes of a graph, and the precedence relationships, represented by the edges (i.e., interconnecting lines). If two nodes are connected by an edge, then the task corresponding to the lower node must complete before the task corresponding to the upper node begins. The scheduling procedure yields as output a schedule of the tasks which respects the precedence relationships. The processors are shown on the horizontal axis, and time on the vertical axis. The makespan of the schedule is also denoted.
In "Complexity of Scheduling Parallel Task Systems", SIAM Journal of Discrete Mathematics (1989), J. Du and J. Leung show that the malleable scheduling problem is NP-hard in the strong sense, even in the special case when there are no precedence constraints. (Mathematically, this means that is highly unlikely that an efficient procedure can be found to find a totally optimal solution to the problem.) No procedure for attempting a solution is developed in this work.
In "Scheduling and Processor Allocation For the Execution of Multi-Join Queries in a Multiprocessor System", Proc. IEEE Conference on Data Engineering (1992), M.-S. Chen, P. Yu and K.-L. Wu consider the malleable scheduling problem in the context of a single query with precedence and general task execution times. The case of multiple queries is not considered in this work, and the procedure developed for a single query finds a solution which is not always very effective.
The nonprecedence version of the malleable scheduling problem is studied in three earlier works. Each of these works considered general task execution times and each proposed one or more procedures.
In "Approximate Algorithms for Scheduling Parallelizable Tasks", Proc. Symposium on Parallel Algorithms and Architectures (1992) by J. Turek, J. Wolf and P. Yu, a class of malleable procedures is presented, each of which is based on procedures for nonmalleable scheduling without precedence, and each of which matches the worst case asymptotic performance of the corresponding simpler procedure. However, precedence is not considered in this work.
In "Scheduling Parallelizable Tasks: Putting it all on the Shelf", Proc. ACM Sigmetrics Conference (1992) by J. Turek, J. Wolf, K. Pattipati and P. Yu, a shelf procedure is developed which is optimal over the set of all possible shelf-based solutions. (Shelf solutions represent a class of approaches to solving scheduling problems.) Again, precedence is not considered in this work.
The procedure presented in "An Approximation Algorithm for Scheduling Tasks on Varying Partition Sizes in Partitionable Multiprocessor Systems", IBM Research Report 15900 (1990) by R. Krishnamurthi and E. Ma solves what amounts to the special case of packing parallelizable tasks onto a single shelf. Therefore, precedence is also not considered in this work.